package org.chnxi.study.datastructrues.sort;

import java.util.Arrays;
import java.util.Random;

/**
 * 使用冒泡进行排序
 */
public class BubbleSorting {

    public static void main(String[] args) {
        int[] arr = new int[] {3, 9 , -1 , 10 , -2};

        System.out.println("步骤拆解：");

        int tmp = 0;
        //第一次排序，将最大的数放到最后
        for(int j =0 ; j < arr.length - 1 ; j++ ){
            if(arr[j] > arr[j+1]){
                tmp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = tmp;
            }
        }
        System.out.println("第一次排序后："+ Arrays.toString(arr));

        //第二次排序，将第二大的数放在倒数第二位
        for(int j =0 ; j < arr.length - 2 ; j++ ){
            if(arr[j] > arr[j+1]){
                tmp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = tmp;
            }
        }
        System.out.println("第二次排序后："+ Arrays.toString(arr));

        //第三次排序，将第三大的数放在倒数第三位
        for(int j =0 ; j < arr.length - 3 ; j++ ){
            if(arr[j] > arr[j+1]){
                tmp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = tmp;
            }
        }
        System.out.println("第三次排序后："+ Arrays.toString(arr));

        //第四次排序，将第四大的数放在倒数第四位
        for(int j =0 ; j < arr.length - 2 ; j++ ){
            if(arr[j] > arr[j+1]){
                tmp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = tmp;
            }
        }
        System.out.println("第四次排序后："+ Arrays.toString(arr));

        System.out.println("步骤合并后：");
        int[] arr2 = new int[] {3, 9 , -1 , 10 , -2};
        for(int i = 0 ; i < arr2.length - 1 ; i++){
            for(int j =0 ; j < arr2.length -(i+1)  ; j++ ){
                if(arr2[j] > arr2[j+1]){
                    tmp = arr2[j];
                    arr2[j] = arr2[j+1];
                    arr2[j+1] = tmp;
                }
            }
            System.out.println("第"+(i+1)+"次排序后："+ Arrays.toString(arr2));
        }

        System.out.println("优化后：");
        int[] arr3 = new int[] {3, 9 , -1 , 10 , 20};
        boolean flag = false;
        for(int i = 0 ; i < arr3.length - 1 ; i++){
            for(int j =0 ; j < arr3.length -(i+1)  ; j++ ){
                if(arr3[j] > arr3[j+1]){
                    flag = true;
                    tmp = arr3[j];
                    arr3[j] = arr3[j+1];
                    arr3[j+1] = tmp;
                }
            }
            if(!flag){
                System.out.println("已经排序完成，跳出多余步骤");
                break;
            }else{
                flag = false;
            }
            System.out.println("第"+(i+1)+"次排序后："+ Arrays.toString(arr3));
        }

        //测试大量数据
        System.out.println("测试大量数据的执行耗时：");
        int[] randomArr = new int[80000];
        for (int i =0; i<80000; i++){
            int num = (int)(Math.random()*80000);
            randomArr[i] = num;
        }
        long start = System.currentTimeMillis();
        bubbleSorting(randomArr);
        long end = System.currentTimeMillis();
        System.out.println("执行耗时："+(end - start));

    }

    public static void bubbleSorting(int[] arr){
        boolean flag = false;
        int tmp = 0;
        for(int i = 0 ; i < arr.length - 1 ; i++){
            for(int j =0 ; j < arr.length -(i+1)  ; j++ ){
                if(arr[j] > arr[j+1]){
                    flag = true;
                    tmp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = tmp;
                }
            }
            if(!flag){
                System.out.println("已经排序完成，跳出多余步骤");
                break;
            }else{
                flag = false;
            }
        }
    }

}
